#include <iostream>
#include <climits>

// 实现Floyd-Warshall算法，计算所有顶点对之间的最短路径
// graph: 代表图的邻接矩阵，V: 顶点的数量
void floydWarshall(int graph[][4], int V) {
    const int MAX_V = 4; // 假设最大顶点数为4
    if (V <= 0 || V > MAX_V) {
        std::cerr << "Invalid number of vertices: " << V << std::endl;
        return;
    }

    int dist[V][V];

    // 初始化dist数组，将每对顶点间的初始距离设置为图中的权重
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            dist[i][j] = graph[i][j];
        }
    }

    // 核心算法，通过逐步引入中间顶点来更新每对顶点间的最短路径
    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                // 如果经过顶点k从i到j的路径更短，则更新dist[i][j]
                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX && dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    // 输出所有顶点对之间的最短距离
    std::cout << "Shortest distances between every pair of vertices:" << std::endl;
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (dist[i][j] == INT_MAX) {
                std::cout << "INF\t";
            } else {
                std::cout << dist[i][j] << "\t";
            }
        }
        std::cout << std::endl;
    }
}